#include <iostream>
#include <stdlib.h>
using namespace std;
char* cache[100];
char *xcat(char *s, char *t) 
{ 
  int i = 0, j = 0; 
  char *aux; 

  if( s == NULL || t == NULL) 
    return NULL; 

while(s[i++]); /* da el tamaño de s */ 
while(t[j++]); /* da el tamaño de t */ 

  if((aux = (char*) malloc(i + j + 1)) == NULL) 
    return NULL; 

  for(i = 0; s[i]; aux[i] = s[i], i++); 
    for(j = 0; t[j]; aux[i] = t[j], j++, i++); 

      return aux; 
  } 

  char* fibo(int n){
      if(cache[n]!=NULL){

        cout << "---en cache ---"<<n<< endl;
        return cache[n];
      }else{
        cache[n] = xcat(fibo(n-1) , fibo(n-2));
        cout << "---generado ---------"<<n<<endl;
      }
      cout<<"---retornando"<<endl;
    return cache[n];
  }

  int main(){

       cache[0]="0";
       cache[1]="1";
       cache[2]="10";
       cache[3]="101";
       cache[4]="10110";
       cache[5]="10110101";
       cache[6]="1011010110110";
       cache[7]="101101011011010110101";
       cache[8]="1011010110110101101011011010110110";
       cache[9]="1011010110110101101011011010110110101101011011010110101";

    int a;
    cin >> a; 
    //cout << fibo(a) << endl;
    char *salida = fibo(a);
//  cout << xcat((char*)"hola ", (char*)"mundo");
  //system("PAUSE");
    return 0;
  }

